題目：797. All Paths From Source to Target

連結：https://leetcode.com/problems/all-paths-from-source-to-target/description/

• 等級：Medium

class Solution {
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<List<Integer>> ans = new LinkedList();
        List<Integer> current = new ArrayList();
        current.add(0);
        dfs(0,current,graph,graph.length-1,ans);
        return ans; 
    }
    private void dfs(int src, List<Integer> current, int graph[][], int dest, List<List<Integer>> ans){
        if(src == dest){
            ans.add(new ArrayList(current));
            return;
        }
        for(int n : graph[src]){
            current.add(n);
            dfs(n,current,graph,dest,ans);
            current.remove(current.size()-1);
        }
    }
}

• Time complexity: O(n)
• Space complexity: O(1)

題目：1458. Max Dot Product of Two Subsequences

• 等級：Hard

class Solution {
    public int maxDotProduct(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int m = nums2.length;
        int[][] save = new int[n][m];
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                save[i][j] = Integer.MIN_VALUE;
            }
        }
        
        return dp(nums1, nums2, 0, 0, save);
    }
    
    private int dp(int[] nums1, int[] nums2, int i, int j, int[][] save) {
        int n = nums1.length;
        int m = nums2.length;
        
        if (i == n || j == m) {
            return Integer.MIN_VALUE;
        }
        
        if (save[i][j] != Integer.MIN_VALUE) {
            return save[i][j];
        }
        
        save[i][j] = Math.max(
            nums1[i] * nums2[j] + Math.max(dp(nums1, nums2, i + 1, j + 1, save), 0),
            Math.max(dp(nums1, nums2, i + 1, j, save), dp(nums1, nums2, i, j + 1, save))
        );
        
        return save[i][j];
    }
}

• Time complexity: O(n*m)
• Space complexity: O(n*m)